package com.leetcode.LeetCode精选TOP面试题;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * @author 覃国强
 * @date 2022-07-07 16:54
 */
public class 题库_0207_课程表 {

  static
  class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
      Map<Integer, List<Integer>> preMap = new HashMap<>();
      for (int[] prerequisite : prerequisites) {
        List<Integer> list = preMap.getOrDefault(prerequisite[0], new ArrayList<>());
        list.add(prerequisite[1]);
        preMap.put(prerequisite[0], list);
      }

      // 先学完基础课
      Set<Integer> already = new HashSet<>();
      for (int i = 0; i < numCourses; ++i) {
        if (!preMap.containsKey(i)) {
          already.add(i);
        }
      }

      // 进行拓扑学习
      boolean study = false;
      do {
        study = false;
        for (int i = 0; i < numCourses; ++i) {
          if (!already.contains(i) && already.containsAll(preMap.get(i))) {
            already.add(i);
            study = true;
          }
        }
      } while (already.size() < numCourses && study);

      return already.size() == numCourses;
    }
  }

}
